"""
 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. 
"""

import Queue

class Solution:
    # @param {integer[]} height
    # @return {integer}
    def trap(self, height):
        """
        :type height: []
        """
        if not height:
            return 0

        height.insert(0, 0)
        height.append(0)

        hh = [ 100000000 ] * len(height)
        hh[0] = hh[-1] = 0
        
        l = len(height)
        for i in range(1, l-1):
            hh [i] = max(max(hh[i-1], height[i-1]), height[i])

        for i in range(1, l-1):
            hh [l-1-i] = min(hh[l-1-i], max(max(hh[l-i], height[l-i]), height[l-1-i]))

        ans = 0
        for i in range(1, l-1):
            ans += hh[i] - height[i]

        return ans

if __name__ == '__main__':
    print Solution().trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])
